package com.caochenlei.tree.huffman;

import java.util.*;

//哈夫曼树的实现类
public class HuffmanTree {
    //哈夫曼树的根结点
    private Node root;

    //哈夫曼树构造方法
    public HuffmanTree(List<Node> nodes) {
        root = buildHuffmanTree(nodes);
    }

    //哈夫曼树构造方法
    public HuffmanTree(byte[] sourceBytes) {
        root = buildHuffmanTree(getNodes(sourceBytes));
    }

    //获取树的叶子结点
    public List<Node> getNodes(byte[] sourceBytes) {
        List<Node> nodes = new ArrayList<Node>();
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte sourceByte : sourceBytes) {
            Integer count = counts.get(sourceByte);
            if (count == null) {
                counts.put(sourceByte, 1);
            } else {
                counts.put(sourceByte, count + 1);
            }
        }
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    //构建一棵哈夫曼树
    private Node buildHuffmanTree(List<Node> nodes) {
        //如果为空则直接返回
        if (nodes.isEmpty()) {
            return null;
        }
        //如果nodes只有一个
        if (nodes.size() == 1) {
            Node node = nodes.get(0);
            Node root = new Node(null, node.weight);
            root.left = node;
            root.right = node;
            return root;
        }
        //如果nodes不止一个
        while (nodes.size() > 1) {
            //从小到大排序二叉树结点
            Collections.sort(nodes);
            //取出第一小的二叉树结点
            Node lNode = nodes.get(0);
            //取出第二小的二叉树结点
            Node rNode = nodes.get(1);
            //重新创建一棵新的二叉树
            Node parent = new Node(null, lNode.weight + rNode.weight);
            parent.left = lNode;
            parent.right = rNode;
            //删除已经处理二叉树结点
            nodes.remove(lNode);
            nodes.remove(rNode);
            //将新的二叉树重新入集合
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    //哈夫曼树根结点
    public Node getRoot() {
        return root;
    }

    //层序遍历当前树
    public void layerErgodic() {
        if (root != null) {
            layerErgodic(root);
        }
    }

    //层序遍历指定树
    private void layerErgodic(Node x) {
        //创建一个队列
        Queue<Node> nodes = new LinkedList<>();
        //加入指定结点
        nodes.offer(x);
        //循环弹出遍历
        while (!nodes.isEmpty()) {
            //从队列中弹出一个结点，输出当前结点的信息
            Node n = nodes.poll();
            System.out.println(n);
            //判断当前结点还有没有左子结点，如果有，则放入到nodes中
            if (n.left != null) {
                nodes.offer(n.left);
            }
            //判断当前结点还有没有右子结点，如果有，则放入到nodes中
            if (n.right != null) {
                nodes.offer(n.right);
            }
        }
    }
}
